package array;

public class KadaneAlgorithm {
    public static int Kadane(int[] a) {
        int globalSum = Integer.MIN_VALUE, runningSum = 0;
        int startIndex = 0, endIndex = 0;
        int startIndexCurrent = 0;

        for (int i = 0; i < a.length; i++) {
            runningSum += a[i];
            if (runningSum > globalSum) {
                globalSum = runningSum;
                startIndex = startIndexCurrent;
                endIndex = i;
            }

            if (runningSum < 0) {
                runningSum = 0;
                startIndexCurrent = i + 1;
            }
        }
        System.out.println("[" + startIndex + ".." + endIndex + "]");
        return globalSum;
    }

    public static void main(String[] args) {

        final int[] numbers = {2, -1, -2, 1, -4, 2, 8};
//        int maxSum = Kadane(numbers);
//        for (int i = 0; i < numbers.length; i++) numbers[i] = -numbers[i];
//        int minSum = -Kadane(numbers);
//
//        System.out.println("maxsum = " + maxSum);
//        System.out.println("minsum = " + minSum);
//        System.out.println("Abs Diff = " + (maxSum - minSum));
        System.out.println();
        solveTheProblem(numbers);
    }

    public static void solveTheProblem(int[] a) {
        int[] minFromLeft = new int[a.length], maxFromLeft = new int[a.length];
        int[] minFromRight = new int[a.length], maxFromRight = new int[a.length];

        int runningMaxSum = 0, runningMinSum = 0;
        int globalMax = Integer.MIN_VALUE, globalMin = Integer.MAX_VALUE;

        for (int i = 0; i < a.length; i++) {
            runningMaxSum += a[i];
            runningMinSum += a[i];
            if (runningMaxSum > globalMax) {
                globalMax = runningMaxSum;
            }
            if (runningMinSum < globalMin) {
                globalMin = runningMinSum;
            }
            if (runningMaxSum < 0) runningMaxSum = 0;
            if (runningMinSum > 0) runningMinSum = 0;

            minFromLeft[i] = globalMin;
            maxFromLeft[i] = globalMax;
        }

        runningMaxSum = 0;
        runningMinSum = 0;
        globalMax = Integer.MIN_VALUE;
        globalMin = Integer.MAX_VALUE;

        for (int i = a.length - 1; i >= 0; i--) {
            runningMaxSum += a[i];
            runningMinSum += a[i];
            if (runningMaxSum > globalMax) {
                globalMax = runningMaxSum;
            }
            if (runningMinSum < globalMin) {
                globalMin = runningMinSum;
            }
            if (runningMaxSum < 0) runningMaxSum = 0;
            if (runningMinSum > 0) runningMinSum = 0;

            minFromRight[i] = globalMin;
            maxFromRight[i] = globalMax;
        }

        int bestResult = 0, splitPoint = 0;
        for (int i = 0; i < a.length; i++) {
            int minimumFromLeft = minFromLeft[i];
            int maximumFromLeft = maxFromLeft[i];

            int minimumFromRight = (i<a.length-1 ? minFromRight[i+1] : 0);
            int maximumFromRight = (i<a.length-1 ? maxFromRight[i+1] : 0);

            if (maximumFromRight - minimumFromRight > bestResult) {
                bestResult = maximumFromRight - minimumFromRight;
                splitPoint = i;
            }
            if (maximumFromLeft - minimumFromLeft > bestResult) {
                bestResult = maximumFromLeft - minimumFromRight;
                splitPoint = i;
            }
        }
        System.out.println("The best result is: " + bestResult + " with a split on " + splitPoint);

    }
}
